package com.dyz.LeetCodeforSwordFingerOffer;

import java.util.ArrayList;

public class Exchange21 {
    public int[] exchange(int[] nums) {
        if(nums.length<=1){
            return nums;
        }
        //双数组方式
        ArrayList<Integer> list1 = new ArrayList<>();
        ArrayList<Integer> list2 = new ArrayList<>();
        for(int i=0; i<nums.length;i++){
            if(nums[i]%2==0){
                list2.add(nums[i]);
            }else {
                list1.add(nums[i]);
            }
        }

        int[] ans =  new int[nums.length];
        int size = 0;
        for (int val:list1){
            ans[size++] = val;
        }
        for(int val : list2){
            ans[size++] = val;
        }
        return ans;
    }

    public int[] exchange1(int[] nums) {
        if (nums.length <= 1) {
            return nums;
        }
        //定义头指针 left，尾指针 right .
        //left 一直往右移，直到它指向的值为偶数
        //right 一直往左移， 直到它指向的值为奇数
        //交换 nums[left] 和 nums[right] .
        //重复上述操作，直到 left == right

        int left = 0;
        int right = nums.length - 1;
        int temp;
        while (left < right) {
            if (nums[left] % 2 == 0 && nums[right] % 2 != 0) {
                temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
            if (nums[left] % 2 != 0) {
                left++;
            }
            if (nums[right] % 2 == 0) {
                right--;
            }
        }
        return nums;
    }
}
